import java.util.*;

public class Leet103 {
    /**
     * 103. 二叉树的锯齿形层序遍历
     * 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     * 例如：
     * 给定二叉树 [3,9,20,null,null,15,7],
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回锯齿形层序遍历如下：
     * [
     * [3],
     * [20,9],
     * [15,7]
     * ]
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        int cixu = 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (queue.size() != 0) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int n = queue.size();
            if (cixu % 2 == 0) {
                for (int i = 0; i < n; i++) {
                    TreeNode treeNode = queue.removeFirst();
                    arrayList.add(treeNode.val);

                    if (treeNode.left != null) {
                        queue.add(treeNode.left);
                    }
                    if (treeNode.right != null) {
                        queue.add(treeNode.right);
                    }
                }

                if (lists.size() % 2 == 1) {
                    Collections.reverse(arrayList);
                }

                lists.add(arrayList);
            }

        }
        return lists;
    }
}